ECE 6605 - Information Theory

Prof. Matthieu Bloch

Tuesday, November 28, 2023

Announcements

  • Project
    • Send me an email to confirm your choices (the sooner the better)
    • I'll hold project office hours to help you
  • Exam options
    • Oral: list of problems published, scheduling options coming
    • Written: Thursday, December 14 11:20 am - 2:10 pm
  • Last time
    • Wiretap channel
  • Today
    • Secret key generation
    • Covert communications

Review: Shannon Cipher System

Image
Shannon Cipher system
  • Historical paper: Claude E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, (1948)
  • Secrecy metric: \(\mathbb{I}(M;C)=0\) - message and ciphertext should be statisticall independent
    • If true, the best attack is to guess the message
  • How is this possible? Secret key is required
    • One-time pad, see assignments
    • How much key do we need? \(\mathbb{H}(K)\geq \mathbb{H}(M)\)

Review: Wiretap channel

Image
Wyner's wiretap channel
  • Historical paper: A. D. Wyner, The Wire-Tap Channel, Bell System Technical Journal, (1975)
    • Physically degraded channel (can be relaxed, more complicated)
  • Secrecy metric: \(\lim_{n\to\infty} \mathbb{I}(M;Z^n)=0\) (asymptotic independence)

A \((n,M_n)\) code \(\calC\) for a wiretap channel consists of an encoding function \(f_n:\{1,\cdots,M_n\}\to\calX^n\) and a decoding function \(g_n:\calY^n\to\{1,\cdots,M_n\}\)

  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)
    2. Reliability and secrecy \(P_e^{(n)}\eqdef \P{\widehat{M}\neq M}\) and \(S^{(n)}\eqdef \mathbb{I}(M;Z^n)\)

Review: Wiretap channel

  • Define \[ C_{\textsf{s}}\eqdef \sup\left\{R: \exists \set{(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log M_n}{n}\geq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=\lim_{n\to\infty}S^{(n)}=0\right\} \]

For a physically degraded discrete memoryless channel characterized by \(P_{Y|X}\) and \(P_{Z|X}\), \[C_{\textsf{s}} = \max_{P_X}\left(\mathbb{I}(X;Y)-\mathbb{I}(X;Z)\right) = \max_{P_X}\mathbb{I}(X;Y|Z)\]

  • Challenges
    • How do we operationalize secrecy?
    • Can we leverage the coding mechanisms studied earlier? (channel coding + soft covering)

Secret key generation

Image
Secret key generation from correlated observations
  • Public authenticated channel of unlimited capacity available for reocnciliation

A \((n,K_n)\) code \(\calC\) for secret-key generation consists of an encoding function \(f_n:\calX^n\to \{1,\cdots,K_n\}\times\calF\) and a decoding function \(g_n:\calY^n\times\calF\to\{1,\cdots,K_n\}\)

  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 K_n}{n}\) (bits/source symbol)
    2. Reliability and secrecy \(P_e^{(n)}\eqdef \P{\widehat{K}\neq K}\) and \(S^{(n)}\eqdef \mathbb{I}(M;(K,Z^n))\)

Secret key generation

  • Define \[ C_{\textsf{sk}}\eqdef \sup\left\{R: \exists \set{(f_n,g_n)}_{n\geq 1} \textsf{ with }\lim_{n\to\infty}\frac{\log K_n}{n}\geq R \text{ and } \lim_{n\to\infty}P_e^{(n)}=\lim_{n\to\infty}S^{(n)}=0\right\} \]

For a physically degraded discrete memoryless channel characterized by \(P_{Y|X}\) and \(P_{Z|X}\), \[C_{\textsf{sk}} = \mathbb{H}(X|Z)-\mathbb{H}(X|Y) = \mathbb{I}(X;Y|Z)\]

  • Not different from secrecy capacity, but this is an artefact of physically degraded channels
    • In general, secret key generation rates are higher than wiretap coding rates.
  • Challenges
    • How do we operationalize secrecy?
    • Can we leverage the coding mechanisms studied earlier?

Covert communications

Image
Covert communication model
  • Pioneering work paper: B.A Bash et al., Limits of Reliable Communication with Low Probability of Detection on AWGN Channels, IEEE Journal on Selected Areas in Communications, (2013)
  • Covertness metric: \(\lim_{n\to\infty} \mathbb{D}(\widehat{Q}^n\Vert Q_0^{\otimes n})=0\) (asymptotic independence)

A \((n,M_n)\) code \(\calC\) for a wiretap channel consists of an encoding function \(f_n:\{1,\cdots,M_n\}\to\calX^n\) and a decoding function \(g_n:\calY^n\to\{1,\cdots,M_n\}\)

  • The performance of an \((n,M_n)\) code is measured in terms of
    1. The rate of the code \(R\eqdef \frac{\log_2 M_n}{n}\) (bits/source symbol)
    2. Reliability and covertness \(P_e^{(n)}\eqdef \P{\widehat{M}\neq M}\) and \(D^{(n)}\eqdef \mathbb{D}(\widehat{Q}^n\Vert Q_0^{\otimes n})\)